Symbols and NIL

Symbol data-block has the following format:

-------------------------------------------------------
|     7 (data-block words)     | Symbol Type (8 bits) |
-------------------------------------------------------
|               Value Descriptor                      |
-------------------------------------------------------
|                       Function Pointer              |
-------------------------------------------------------
|                     Raw Function Address            |
-------------------------------------------------------
|                        Setf Function                |
-------------------------------------------------------
|                        Property List                |
-------------------------------------------------------
|                          Print Name                 |
-------------------------------------------------------
|                           Package                   |
-------------------------------------------------------

Most of these slots are self-explanatory given what symbols must do in Common Lisp, but a couple require comments. We added the Raw Function Address slot to speed up named call which is the most common calling convention. This is a non-descriptor slot, but since objects are dual word aligned, the value inherently has fixnum low-tag bits. The GC method for symbols must know to update this slot. The Setf Function slot is currently unused, but we had an extra slot due to adding Raw Function Address since objects must be dual-word aligned.

The issues with nil are that we want it to act like a symbol, and we need list operations such as CAR and CDR to be fast on it. CMU Common Lisp solves this by putting nil as the first object in static space, where other global values reside, so it has a known address in the system:

-------------------------------------------------------  <-- space
|                               0                     |      start
-------------------------------------------------------
|     7 (data-block words)     | Symbol Type (8 bits) |
-------------------------------------------------------  <-- nil
|                           Value/CAR                 |
-------------------------------------------------------
|                         Definition/CDR              |
-------------------------------------------------------
|                      Raw Function Address           |
-------------------------------------------------------
|                         Setf Function               |
-------------------------------------------------------
|                         Property List               |
-------------------------------------------------------
|                           Print Name                |
-------------------------------------------------------
|                            Package                  |
-------------------------------------------------------
|                              ...                    |
-------------------------------------------------------

In addition, we make the list typed pointer to nil actually point past the header word of the nil symbol data-block. This has usefulness explained below. The value and definition of nil are nil. Therefore, any reference to nil used as a list has quick list type checking, and CAR and CDR can go right through the first and second words as if nil were a cons object.

When there is a reference to nil used as a symbol, the system adds offsets to the address the same as it does for any symbol. This works due to a combination of nil pointing past the symbol header-word and the chosen list and other-pointer type tags. The list type tag is four less than the other-pointer type tag, but nil points four additional bytes into its symbol data-block.

;;;; Array Headers.

The array-header data-block has the following format:

----------------------------------------------------------------
| Header Len (24 bits) = Array Rank +5   | Array Type (8 bits) |
----------------------------------------------------------------
|               Fill Pointer (30 bits)                   | 0 0 | 
----------------------------------------------------------------
|               Available Elements (30 bits)             | 0 0 | 
----------------------------------------------------------------
|               Data Vector (29 bits)                  | 1 1 1 | 
----------------------------------------------------------------
|               Displacement (30 bits)                   | 0 0 | 
----------------------------------------------------------------
|               Displacedp (29 bits) -- t or nil       | 1 1 1 | 
----------------------------------------------------------------
|               Range of First Index (30 bits)           | 0 0 | 
----------------------------------------------------------------
                              .
                              .
                              .

The array type in the header-word is one of the eight-bit patterns from section "Data-Blocks and Other-immediates Typing", indicating that this is a complex string, complex vector, complex bit-vector, or a multi-dimensional array. The data portion of the other-immediate word is the length of the array header data-block. Due to its format, its length is always five greater than the array's number of dimensions. The following words have the following interpretations and types:

Fill Pointer:: This is a fixnum indicating the number of elements in the data vector actually in use. This is the logical length of the array, and it is typically the same value as the next slot. This is the second word, so LENGTH of any array, with or without an array header, is just four bytes off the pointer to it.
Available Elements:: This is a fixnum indicating the number of elements for which there is space in the data vector. This is greater than or equal to the logical length of the array when it is a vector having a fill pointer.
Data Vector:: This is a pointer descriptor referencing the actual data of the array. This a data-block whose first word is a header-word with an array type as described in sections "Data-Blocks and Header-Word Format" and "Data-Blocks and Other-immediates Typing"
Displacement:: This is a fixnum added to the computed row-major index for any array. This is typically zero.
Displacedp:: This is either t or nil. This is separate from the displacement slot, so most array accesses can simply add in the displacement slot. The rare need to know if an array is displaced costs one extra word in array headers which probably aren't very frequent anyway.
Range of First Index:: This is a fixnum indicating the number of elements in the first dimension of the array. Legal index values are zero to one less than this number inclusively. IF the array is zero-dimensional, this slot is non-existent.
... (remaining slots):: There is an additional slot in the header for each dimension of the array. These are the same as the Range of First Index slot.